#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<stack>
#include<cmath>
#include<string>
#include<unordered_set>
#include<map>
using namespace std;

void solve()
{
    int n, k; cin >> n >> k;
    if (k == 1)
    {
        cout << n << endl; return;
    }
    vector<int> arr;
    arr.push_back(n);
    while (arr.back() >= k)
    {
        int temp = arr.back() / k;
        arr.back() %= k;
        arr.push_back(temp);
    }
    int ans = 0;
    for (auto& x : arr) ans += x;
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}